public class Solution {
    public int waysToStep(int n) {
        int t0 = 1, t1 = 1, t2 = 2;
        int MOD = (int)1e9 + 7;
        if (n == 0) {
            return t0;
        } else if (n == 1) {
            return t1;
        } else if (n == 2) {
            return t2;
        }
        int count = 3;
        int ret = 0;
        while (count <= n) {
            ret = ((t0 + t1) % MOD + t2) % MOD;
            t0 = t1;
            t1 = t2;
            t2 = ret;
            count++;
        }
        return ret;
    }

    public int waysToStep2(int n) {
        int MOD = (int)1e9 + 7;

        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else if (n == 3) {
            return 4;
        }

        int[] ret = new int[n + 1];
        ret[1] = 1;
        ret[2] = 2;
        ret[3] = 4;
        for (int i = 4; i <= n; i++) {
            ret[i] = ((ret[i - 1] + ret[i - 2]) % MOD + ret[i - 3]) % MOD;
        }
        return ret[n];
    }
}
